#pragma once

#ifndef _T2DLINKEDLIST_H_
#define _T2DLINKEDLIST_H_

#include "T2List.h"

template<class T,class D>class T2DLinkedNode;

template<class T,class D>class T2DLinkedList: public T2List<T,D>
{
private:
	T2DLinkedNode<T,D>* root;
	T2DLinkedNode<T,D>* back;
	unsigned int nodeCount;

	T2DLinkedNode<T,D>* elementAt(unsigned int index)//Returns the element at position index
	{
		if ((root==NULL) || (index>=nodeCount))
			return NULL;

		T2DLinkedNode<T,D>* temp=root;
		for (unsigned int i=0; i<index;i++)
		{
			temp=temp->getNext();
		}
		return temp;
	}

	void removeElement(T2DLinkedNode<T,D>* delElement)
	{
		if (delElement==root)
			root=delElement->getNext();
		if (delElement==back)
			back=delElement->getPrev();

		T2DLinkedNode<T,D>* prev=delElement->getPrev();
		T2DLinkedNode<T,D>* next=delElement->getNext();

		if (prev!=NULL)
			prev->setNext(next);
		if (next!=NULL)
			next->setPrev(prev);

		delete delElement;
	}
public:
	T2DLinkedList()
	{
		root = NULL;
		back = NULL;
		nodeCount = 0;
	}

	~T2DLinkedList()
	{
		clear();
	}

	char pushFront(T newKey,D newData)//Adds a new (newKey,newData) tupel to the front of the list
	{
		if ((root!=NULL) && (root->find(newKey)!=NULL))
			return 0;
		
		T2DLinkedNode<T,D>* newElement = new T2DLinkedNode<T,D>(newKey,newData);
		newElement->setNext(root);
		if (root!=NULL)
			root->setPrev(newElement);
		root = newElement;
		nodeCount++;

		if (back==NULL)
			back = newElement;
		return 1;
	}

	char pushBack(T newKey,D newData)//Adds a new (newKey,newData) tupel to the back of the list
	{
		if ((root!=NULL) && (root->find(newKey)!=NULL))
			return 0;

		T2DLinkedNode<T,D>* newElement = new T2DLinkedNode<T,D>(newKey,newData);

		if (root==NULL)
		{
			root = newElement;
			back = newElement;
		}
		else
		{
			back->append(newElement);
			back = back->getNext();
		}
		nodeCount++;
		return 1;
	}

	D find(T seaKey)//Returns the data assoziated with the key seaKey
	{
		if (root==NULL)
			return NULL;

		T2DLinkedNode<T,D>* temp = root->find(seaKey);

		if (temp==NULL)
			return NULL;
		return temp->getData();
	}

	unsigned int getSize()//Returns the number of elements in the list
	{
		return nodeCount;
	}

	void clear()//Removes all elements from the list
	{
		while (root!=NULL)
			removeElement(root);
		nodeCount=0;
	}

	T getKeyAt(unsigned int index)//Returns the key for the element at position <index>
	{
		T2DLinkedNode<T,D>* temp = elementAt(index);
		if (temp==NULL)
			return NULL;

		return temp->getKey();
	}

	D at(unsigned int index)//Returns the element at position index
	{
		T2DLinkedNode<T,D>* temp=elementAt(index);

		if (temp==NULL)
			return NULL;

		return temp->getData();
	}

	D getFirst()//Returns the first element in the list
	{
		if (root == NULL)
			return NULL;
		return root->getData();
	}

	D getLast()//Returns the last element in the list
	{
		if (back == NULL)
			return NULL;
		return back->getData();
	}
private:

	void sortInternal(bool descending)//Sorts the list by key
	{
		if (root == NULL)
			return;

		//For now: Bubblesort
		bool changed=true;
		T2DLinkedNode<T,D>* currElement;
		T2DLinkedNode<T,D>* nextElement;
		while(changed)
		{
			changed=false;
			currElement=root;
			while(currElement->getNext()!=NULL)
			{
				nextElement = currElement->getNext();
				if (descending != (currElement->getKey() > nextElement->getKey()))
				{
					if (currElement == root)
						root = nextElement;
					if (nextElement == back)
						back = currElement;

					//fix the links to the node before the current node
					if (currElement->getPrev()!=NULL)
						currElement->getPrev()->setNext(nextElement);
					nextElement->setPrev(currElement->getPrev());

					//fix the links to the node behind the next node
					if (nextElement->getNext()!=NULL)
						nextElement->getNext()->setPrev(currElement);
					currElement->setNext(nextElement->getNext());

					//fix the links between the current and the next node
					nextElement->setNext(currElement);
					currElement->setPrev(nextElement);

					changed = true;
				}
				currElement = nextElement;
			}
		}
	}
public: 
	void sort()
	//Sorts the list by key
	{
		sortInternal(false);
	}

	void inversesort()
	/*
	Sorts the entries in the list by key (descending).
	Does not work with avl lists, those are always sorted ascending!
	Either use T2AVLListInverted as the backend or search from the back.
	*/
	{
		sortInternal(true);
	}

	char removeByKey(T delKey)//Removes the element with key delKey from the list
	{
		if (root==NULL)
			return 0;

		T2DLinkedNode<T,D>* temp = root->find(delKey);

		if (temp==NULL)
			return 0;

		removeElement(temp);
		nodeCount--;
		return 1;
	}

	char removeAt(unsigned int index)//Removes the element at position index from the list
	{
		T2DLinkedNode<T,D>* temp=elementAt(index);

		if (temp==NULL)
			return 0;

		removeElement(temp);
		nodeCount--;
		return 1;
	}

	char changeKey(T oldKey, T newKey)
	/*
	Changes the key for the data associated with <oldKey> to <newKey>
	Return values:
	0 - success
	1 - node found with key <newKey>
	2 - no node found with key <oldKey>
	3 - 
	*/
	{
		if (root == NULL)
			return 3;
		T2DLinkedNode<T,D>* tempNode;

		tempNode = root->find(newKey);

		if (tempNode != NULL)
			return 1;
		
		tempNode = root->find(oldKey);

		if (tempNode == NULL)
			return 2;

		tempNode->setKey(newKey);
		return 0;
	}
};

template<class T,class D>class T2DLinkedNode
{
private:
	T2DLinkedNode<T,D>* prev;
	T2DLinkedNode<T,D>* next;
	T key;
	D data;
public:
	T2DLinkedNode()
	{
		prev=NULL;
		next=NULL;
	}

	T2DLinkedNode(T newKey, D newData)
	{
		prev=NULL;
		next=NULL;
		key=newKey;
		data=newData;
	}

	/*
	get-functiosn for data + key
	*/

	T getKey()
	{
		return key;
	}

	void setKey(T newKey)
	{
		key = newKey;
	}

	D getData()
	{
		return data;
	}

	/*
	get & set functions for next and prev
	*/

	T2DLinkedNode<T,D>* getNext()
	{
		return next;
	}

	T2DLinkedNode<T,D>* getPrev()
	{
		return prev;
	}

	void setNext(T2DLinkedNode<T,D>* newNext)
	{
		next=newNext;
	}

	void setPrev(T2DLinkedNode<T,D>* newPrev)
	{
		prev=newPrev;
	}

	char append(T2DLinkedNode<T,D>* newElement)
	/*
	Append a new element to the back of the list
	*/
	{
		if (key==newElement->getKey())
			return 0;

		if (next!=NULL)
			return next->append(newElement);

		next = newElement;
		newElement->setPrev(this);
		return 1;
	}

	T2DLinkedNode<T,D>* find(T seaKey)
	/*
	Return the node associated with the key <seaKey>
	*/
	{
		if (key==seaKey)
			return this;

		if (next!=NULL)
			return next->find(seaKey);

		return NULL;
	}
};
#endif